package algorithm.swordoff;

/**
 * 二叉搜索树的后续遍历序列
 *
 * 题目:判断一个数组是否为二叉查找树的后序遍历
 * 根据后序遍历最后一个数是根节点,找到左右子树的分界点,递归判断左子树和右子树
 * 4, 8, 6, 12, 16, 14, 10 (begin:0, end:6)
 * left:[4,8,6] (begin:0, end:2) -> left:[4] (begin:0, end:0), right:[8] (begin:1, end:1)
 * right:[12, 16, 14] (begin:3, end:5) -> left:[12] (begin:3, end:3), right:[16] (begin:4, end:4)
 * 显然 递归终点就是begin=end的时候
 */

public class SQ33 {

    public boolean verifyPostorder(int[] postorder) {
        return isPostOrder(postorder, 0, postorder.length-1);
    }

    private boolean isPostOrder(int[] arr, int begin, int end) {
        if (begin >= end) return true;

        int mid = begin;
        while (arr[end] > arr[mid]) mid++;

        int right = mid;
        while (right < end) {
            // 有个提前结束,如果右子树内部存在比根节点还小的元素,直接返回false
            if (arr[right] < arr[end]) return false;
            else right++;
        }
        return isPostOrder(arr, begin, mid-1) && isPostOrder(arr, mid, end-1);
    }

    public static void main(String[] args) {
        int[] a = {4, 8, 6, 12, 16, 14, 10};
        SQ33 sq33 = new SQ33();
        System.out.println(sq33.verifyPostorder(a));
    }
}
